package com.bigshen.algorithm.aLinearList.solution04AddTwoNumbers;

/**
 * ### 2. Add Two Numbers
 *
 * You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
 *
 * You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * ```
 *
 *  * Definition for singly-linked list.
 *  * public class ListNode {
 *  *     int val;
 *  *     ListNode next;
 *  *     ListNode() {}
 *  *     ListNode(int val) { this.val = val; }
 *  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 *  * }
 *
 */
public class Solution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        if (null == l1) {
            return l2;
        }
        if (null == l2) {
            return l1;
        }

        ListNode n1 = l1;
        ListNode n2 = l2;
        ListNode dummy = new ListNode();
        ListNode tmp = dummy;
        int carry = 0;

        // n1、n2节点向后遍历累加，值记录在tmp内
        while (null != n1 && null != n2) {
            ListNode next1 = n1.next;
            ListNode next2 = n2.next;
            Integer sum = n1.val + n2.val + carry;
            carry = sum/10;
            tmp.next = new ListNode(sum%10);

            n1 = next1;
            n2 = next2;
            tmp = tmp.next;
        }

        if (null == n1) {
            // l1链表先遍历完，继续向后遍历l2链表
            while(null != n2) {
                ListNode next = n2.next;
                Integer sum = n2.val + carry;
                carry = sum/10;
                tmp.next = new ListNode(sum%10);

                n2 = next;
                tmp = tmp.next;
            }
        }

        if (null == n2) {
            // l2链表先遍历完，继续向后遍历l1链表
            while(null != n1) {
                ListNode next = n1.next;
                Integer sum = n1.val + carry;
                carry = sum/10;
                tmp.next = new ListNode(sum%10);

                n1 = next;
                tmp = tmp.next;
            }
        }

        // 遍历结束
        if (carry != 0) {
            tmp.next = new ListNode(carry);
        }

        return dummy.next;

    }

}

